import sortedcontainers
class Solution(object):
    def oddEvenJumps(self, arr):
        list_st = sortedcontainers.SortedList()
        drop_st = sortedcontainers.SortedList()
        n = len(arr)
        next_lift = [-1] * n
        next_drop = [-1] * n
        for i in range(n - 1, -1, -1):
            list_index = list_st.bisect_left([arr[i], i])
            if list_index < len(list_st):
                next_lift[i] = list_st[list_index][1]
            list_st.add([arr[i], i])
            drop_index = drop_st.bisect_left([-arr[i], i])
            if drop_index < len(drop_st):
                next_drop[i] = drop_st[drop_index][1]
            drop_st.add([-arr[i], i])
        ans_lift = [0] * n
        ans_drop = [1] * n
        for i in range(n):
            if next_lift[i] != -1:
                ans_lift[next_lift[i]] += ans_drop[i]
            if next_drop[i] != -1:
                ans_drop[next_drop[i]] += ans_lift[i]
        return ans_lift[-1] + ans_drop[-1]


    
data = Solution()
# arr = [10,13,12,14,15]
# print(data.oddEvenJumps(arr))
arr = [1,2,3,2,1,4,4,5]
print(data.oddEvenJumps(arr))
